package cn.edu.jxau.test;

import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

//--------------------------
// 解法1：切分
//--------------------------
//public class Main {
//
//	public static void main(String[] args) {
//
//		int[] arr = new int[] { 4, 5, 1, 6, 2, 7, 3, 8 };
//		k(arr, 4);
//	}
//
//	private static void k(int[] arr, int k) {
//
//		Objects.requireNonNull(arr, "参数arr为不能为null");
//		if (k <= 0) {
//			throw new IllegalArgumentException(String.format("k=%d,k要大于零", k));
//		}
//		if (k > arr.length) {
//			throw new IllegalArgumentException(String.format("k=%d,arr的数组元素不足k个", k));
//		}
//		int low = 0;
//		int high = arr.length - 1;
//		int p = partition(arr, low, high);
//		while (p != k - 1) {
//			if (p < k - 1) {
//				low = p + 1;
//			} else {
//				high = p - 1;
//			}
//			p = partition(arr, low, high);
//		}
//		for (int i = 0; i < k; i++) {
//			System.out.println(arr[i] + " ");
//		}
//
//	}
//
//	private static int partition(int[] arr, int low, int high) {
//
//		int p = arr[low];
//		while (low < high) {
//			while (low < high && p < arr[high]) {
//				high--;
//			}
//			if (low < high) {
//				arr[low++] = arr[high];
//			}
//			while (low < high && arr[low] < p) {
//				low++;
//			}
//			if (low < high) {
//				arr[high--] = arr[low];
//			}
//		}
//		arr[low] = p;
//		return low;
//	}
//
//	private static void swap(int[] arr, int i, int j) {
//
//		int temp = arr[i];
//		arr[i] = arr[j];
//		arr[j] = temp;
//	}
//}

//--------------------------
//解法2：优先队列
//--------------------------
public class Main {

	public static void main(String[] args) {

		int[] arr = new int[] { 4, 5, 1, 6, 2, 7, 3, 8 };
		k(arr, 4);
	}

	private static void k(int[] arr, int k) {

		Queue<Integer> queue = new PriorityQueue<>(k,Collections.reverseOrder());
		for (int i = 0; i < k; i++) {
			queue.offer(arr[i]);
		}
		for (int i = k; i < arr.length; i++) {
			if (queue.peek() > arr[i]) {
				queue.poll();
				queue.offer(arr[i]);
			}
		}
		for (int i = 0; i < k; i++) {
			System.out.println(queue.poll() + " ");
		}
	}
}